\documentclass{article}
\usepackage{fullpage}

% Use a small font for the verbatim environment
\makeatletter  % makes '@' an ordinary character
\renewcommand{\verbatim@font}{%
  \ttfamily\footnotesize\catcode`\<=\active\catcode`\>=\active%
}
\makeatother   % makes '@' a special symbol again

\begin{document}

\begin{titlepage}
\begin{center}

\vspace*{3in}

{\huge Pigasus}

{\it The Whitepaper}

\vspace*{0.5in}

COMS W4115

\today

\vfill

\end{center}

\begin{flushright}

{\bf Team Hogzilla}

{\it Project Manager:} John Zhang (jrz2106)

{\it System Architect:} Sharath Gururaj (sa2617)

{\it System Integrator:} Artem Shnayder (as2827)

{\it Language Guru:} Jordan Rupprecht (jjr2119)

{\it Verification and Validation Person:} Philip Tjimos (pmt2103)

\end{flushright}
\end{titlepage}

\section*{Introduction}

We introduce the Pigasus programming language. Pigasus is a light-weight language designed for distributing computing jobs across an arbitrary network to allow programmers to make use of multiple machines concurrently.

In many scenarios, programmers may be presented with problems that are clearly parallelizable, that is, programs with routines that can run on different sets of input data independently. Solutions to these problems can execute more efficiently by taking advantage of multiple threads or machines. For programmers with the need to execute computationally-intensive programs and have access to a number of networked machines and high bandwidth, the advantage of distributing a program onto multiple machines is clear.

Similarly, there are many scenarios where a programmer may need to execute a single-threaded program on multiple data inputs. Common examples include software testing, or scientific simulations. Automating the execution of these tasks on multiple machines would save time and effort.

Pigasus addresses both these situations (and possibly others) with an emphasis on the latter. Programmers will be able to write a program (using any other language) to create an executable binary and use Pigasus to distribute the binary and specify and manipulate the different input sets and gather the output. Thus, programmers will be able to focus on writing the code to solve their problem and minimize their need to deal with the task of managing the network and distributing their code.

\section*{Motivation}

Pigasus was motivated by the work of two of the team members.  In a previous course project, a resource-intensive simulation needed to be run on several data sets with many different configurations. Ultimately, a more efficient approach was taken by distributing the workload across the machines in the students' computing cluster. This was done by automating the process of manipulating the configurations and distributing the script and associated binaries to the cluster machines and executing remotely. This was accomplished using Python and Bash scripts. Of course the solution was ad-hoc and time consuming to implement.

Our group realized that the solution could be generalized to cater to similar distributed problems. The main target groups of our language would be students and researchers who want to run heavy simulations without investing in extensive hardware, or the time to set up such an environment.

\section*{Existing Work}

Two of the most popular distributed frameworks currently used are MapReduce and Hadoop.

MapReduce is a software framework created by Google to process large datasets using their large computing clusters. It is a specialized framework implemented in existing languages such as Java and C++ so software using MapReduce must conform to a specification. The remote machines must also conform to a certain setup but have powerful features including data replication and load balancing. The MapReduce model is divided into the ``map'' and ``reduce'' phases. In the map phase, input data is split into chunks and the mapper routine is applied on each chunk independently. The results of the map phase are separated according to keys and, for each key, merged according to the reduce routine.

Hadoop is an open source implementation of MapReduce used by, among others, Yahoo to run their search algorithms.

The extensive setup required and the specialized code make it impractical for private individuals. While Pigasus lacks some of the power of MapReduce and Hadoop, it has the advantage of being simple and extensible from existing binaries. Software does not need to be written especially for Pigasus, and remote machines do not require the specialized setup.

\section*{Buzzwords}

Pigasus is simple, distributed, secure and system integrated.

\subsection*{Simple}

Pigasus code will be clean, compact, and easy-to-read. Using Pigasus, programmers will have the ability to run jobs on multiple machines across a network with a minimal amount of code related to network programming, load balancing or secure communication.

Furthermore, Pigasus requires no special setup for remote machines. All that will be required to use a remote machine is that it be running a Unix-based system (e.g. Linux or Mac) and is accessible by the programmer via SSH / SCP (i.e. the programmer has an account on that machine). This is an advantage over many existing distributed frameworks such as MapReduce and Hadoop which require special software running on the remote clusters before using them (although these frameworks are considerably more powerful).

\subsection*{Distributed}

This language will allow programmers to send jobs to multiple computers/servers in order to execute arbitrary programs with different inputs. The same program can be sent over a network and executed several times, with different or same inputs, with data collected at the end. This allows someone from a laptop or a cheap PC to run resource intensive processes on a computing cluster as if it were their own computer.

\subsection*{Secure}

Utilizing SSH will allow for secure transfer of data, user names, passwords, and anything else that the programmer may send and receive. Since all remote commands are issued through the shell under the user's permissions, all the actions are restricted to those same permissions. The user wouldn't be able to do anything that they couldn't already do sitting at the machine physically.

\subsection*{System Integrated}

Pigasus programmers will easily be able to access the shell. If something cannot be accomplished efficiently with Pigasus, or if there is already existing code written, Pigasus can instead interact with that code. Pigasus can simply provide the input and/or process the output. This would be useful, for example, if you are forced to use a closed-source binary as part of your simulations, and there is no other way to produce the output that the binary can.

\section*{Applications}

Use of Pigasus may be beneficial for anyone with access to a group of networked machines (particularly if these machines are often idle) and high bandwidth, while operating on a low budget and therefore cannot afford to purchase computing time on a large computing cluster such as Amazon's EC2 service. Students, researchers, engineers working at small companies may find this particularly useful. In the near future, this may also be useful for mobile computing, as battery-sensitive devices can utilize remote CPU power instead of draining their own batteries. Some possible applications include:

\begin{itemize}

\item Distributed 3D rendering.
\subitem Often, a large number of 3D images need to be rendered. A raytracer could be written in C/OpenGL, compiled and pushed out to multiple machines where different images are rendered based on the parameters.
\item Distributed code compilation.
\subitem Source code for large software engineering projects may be pushed out to multiple machines and compiled individually (e.g. produce object files for C code). Then, they can be pulled back to the host machine where they can be linked together. One example of an existing distributed compiler is distcc.
\item Research simulations.
\subitem In many areas of research, simulations need to be run on different data sets. The benefit of distributing the simulations is clear.
\item Pushing single jobs to a remote machine.
\subitem Many students own low-powered laptops. Pushing large computing jobs (e.g. an assignment) out to a remote machine would enable the student to use their laptop for other purposes.

\end{itemize}

There are also many situations where people not falling in one of the aforementioned categories may find Pigasus useful. For example:

\begin{itemize}
\item Setup several machines simultaneously.
\subitem Suppose a person owns multiple machines (e.g. a desktop and a laptop) and wishes to install the same set of software on them. After installing Linux and SSH manually (which is often automatic in the installation of Linux), Pigasus can be used to distribute and run shell scripts to configure the machines simultaneously. Pigasus does {\it not} need to be configured on the remote computers for this to be done.

\end{itemize}
 
\section*{Sample Code}

Three examples of Pigasus code are provided here. The first is the Pigasus version of the classic ``hello world'' program where a remote machine is commanded to print \verb|hello world| to the standard output which is then pulled back to the host machine.

\begin{quote}
\begin{verbatim}
// We'll use Java/C++ style comments and templates. Square brackets denote a
// list. Note that the Server type is a specialized list, with the elements
// being (in order): th remote machine, username, password, and path to private
// key (if applicable).
List<Server> servers = [ 
  [ "compute.cs.columbia.edu", "student", "pass", null ]
];

// All functions with return type Job are executed on a remote machine. They are
// passed a unique job_id first.
Job HelloWorldJob(Integer job_id) {
  ExecuteShellCommand("echo \"Hello World!\"");
}

// The Main function is the program entry point.
Main(List<String> argv) {
  Connect(servers);

  // RunJob is a special function which automatically pushes a single job out 
  // to a machine and returns the job_id. 
  Integer job_id = RunJob(HelloWorldJob);

  // Output is a special structure used to access the files (including stderr,
  // stdout) returned by remote machines. We also adopt the Python % operator,
  // which is essentially a StringPrintf(). Furthermore, all lists will be
  // associative and accessible by strings as well as integers.
  Print("%s\n", % Output[job_id].GetStdout());
}
\end{verbatim}
\end{quote}

One of the sample applications listed was a Pigasus implementation of a
distributed compiler such as distcc. While distcc has advanced options, the
basic functionality would be easy to implement using Pigasus.

\begin{quote}
\begin{verbatim}
// We'll demonstrate how multiple servers can be listed here. We introduce the 
// ~n operator, which makes a value the default value across the n-th dimension
// (1st dimension would be rows, 2nd would be columns, etc.). The benefit of 
// using a matrix to specify servers is that the specification could be created
// using a common spreadsheet editor and saved as a CSV file, which could be 
// imported with a special Pigasus function.
List<Server> servers = [
  [ "compute01.cs.columbia.edu", "student"~2, "pass"~2, null~2          ],
  [ "compute02.cs.columbia.edu",            ,         ,                 ],
  [ "compute08.cs.columbia.edu",            ,         ,                 ],
  [ "clic.cs.columbia.edu"     , "alice"    ,         , "~/.ssh/id_rsa" ]
];

Job CompileFileJob(Integer job_id) {
  String c_source = Inputs[job_id].GetFileName();

  // This will produce the object file <job_id>.o.
  ExecuteShellCommand("gcc -c %s -o %d.o" % [c_source, job_id]);
}

Main(List<String> argv) {
  // Inputs is a special variable containing files / data associated with each
  // job separated by job ID. We also adopt Python 'slice' notation, so 
  // argv[1:] returns all elements of argv minus the first one.
  Inputs = LoadFilesToSend(argv[1:]);

  Connect(servers);
  
  List<Integer> job_ids = RunJobs(CompileFileJob);

  String link_cmd = "gcc";
  Boolean success = True;
  for (Integer j in job_ids) {
    if (Output[j].GetStderr() != "") {
      Print("Error found in file %s:\n%s\n\n" % [ Inputs[j].GetFileName(),
                                                  Output[j].GetStderr() ]);
      success = False;
      break;
    }
    link_cmd += " " + j + ".o";
  }

  // Link to produce a.out.
  if (success) {
    ExecuteShellCommand(link_cmd);
  }    
}

\end{verbatim}
\end{quote}

\section*{Conclusion}

The goal of Pigasus, as seen in the sample code, is to make distributing jobs
very simple and straightforward. Since the only prerequisite for Pigasus is a UNIX environment, with tools such as SSH, it can be run on almost any non-Windows computer. We have identified many categories of users and applications which might find Pigasus useful. There are many other applications which would be simple given a language like Pigasus. 

\end{document}
